// https://leetcode.cn/problems/fruit-into-baskets/description/

// 算法思路总结：
// 1. 使用滑动窗口维护最多包含两种水果的区间
// 2. 哈希表记录窗口内水果种类和数量
// 3. 当种类超过两种时，左指针收缩窗口
// 4. 实时更新最大窗口长度
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <unordered_map>

class Solution 
{
public:
    int totalFruit(vector<int>& fruits) 
    {
        int n = fruits.size(), ret = 0;
        unordered_map<int, int> up;

        for (int l = 0, r = 0 ; r < n ; r++)
        {
            up[fruits[r]]++;
            while (up.size() > 2)
            {
                up[fruits[l]]--;
                if (up[fruits[l]] == 0) 
                    up.erase(fruits[l]);
                l++;
            }
            ret = max(ret, r - l + 1);
        }
        return ret;
    }
};

int main()
{
    vector<int> v1 = {1,2,1}, v2 = {3,3,3,1,2,1,1,2,3,3,4};
    Solution sol;

    cout << sol.totalFruit(v1) << endl;
    cout << sol.totalFruit(v2) << endl;

    return 0;
}